package _17_树的子结构;
/*
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */

/**
 * 思路：   这个题是说B是A的左子树之一或者右子树之一或者从根开始相同
 *      先看根节点的值相同与否，若同，则直接调用match(A,B)
 *      若不等，先match A.left和b，若返回false，则match A.right和B
 *      match函数逻辑：当B用完了，为null时，无论A是null还是有值，都返回true
 *                   当B没用完，A用完时，返回false
 *                   当A和B的值不同时，返回false，说明不匹配
 *
 *                   当A和B的节点值是相同的时候，递归调用match函数 A左和B左 与A右和B右同时成立时返回true
 *
 *
 *
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null ||root1==null) return false;
        else{
            boolean result=false;
            if(root1.val ==root2.val){
                result = match(root1,root2);
            }
            if(result==false){
                result = match(root1.left,root2);
            }
            if(result == false){
                result = match(root1.right,root2);
            }
            return result;
        }

    }

    public boolean match(TreeNode root1, TreeNode root2){
        if(root2==null){
            return true;
        }
        if(root1==null){
            return false;
        }
        if(root1.val !=root2.val){
            return false;
        }

        return match(root1.left,root2.left) &&match(root1.right,root2.right);
    }
}
